Intro

堆疊,佇列
在添加貨刪除時有更多控制的資料結構

佇列

• FIFO 先進先出
• almost like Stack, 添加和移除元素的原則不同
  • enqueue(), dequeue, front, isEmpty, size
  • 只能用enqueue和dequeue 去添加or刪除堆疊中元素 => FIFO

應用

1. 優先序列：元素的添加和移除是基於優先級的

• ex 急診 , 頭等艙vs商務艙
• how兩種選項
  1. 設定優先級 在正確位置添加元素
  2. 用入列操作添加元素,按照優先級移除它們
• 分類
  • 最小優先 1最先
  • 最大優先 1最後

2. 環狀佇列

• 重點: queue.enqueue(queue.dequeue()) 離開a後 先剔除a(dequeue從最前面移除)再加入(enqueue加入到最後面)形成環狀

//建立佇列
function Queue(){
  var items = []
  this.enqueue = function(element){
    items.push(element)
  }
  this.dequeue = function() {
    return items.shift()
  }
  this.front = function(){
    return items[0]
  }
  this.isEmpty = function(){
    return items.length == 0
  }
  this.size = function(){
    return items.length
  }
  this.clear = function(){
    items = []
  }
}
//使用佇列
var queue = new Queue()

//優先佇列

function PriorityQueue(){
  let items = []

  function QueueElement (element, priority){
    this.element = element
    this.priority = priority
  }
  this.enqueue = function(element, priority){
    let queueElement = new QueueElement(element, priority)
    if(this.isEmpty()){
      items.push(queueElement)
    }
    else {
      let added = false
      for (let i = 0; i < items.length ; i++){
        if(queueElement.priority < items[i].priority){
          items.splice(i,0,queueElement)
          added = true
          break
        }
      }
      if (!added){
        items.push(queueElement)
      }
    }
  }
  this.dequeue = function() {
    return items.shift()
  }
  this.front = function(){
    return items[0]
  }
  this.isEmpty = function(){
    return items.length == 0
  }
  this.size = function(){
    return items.length
  }
  this.clear = function(){
    items = []
  }
}

//使用優先佇列- 燙手山芋
var priorityqueue = new PriorityQueue()

//環狀佇列
function hotPotato(nameList, num){
  let queue = new Queue()
  for (let i =0 ; i< nameList.length; i++){
    queue.enqueue(nameList[i])
  }

  let eliminated = ''
  while (queue.size() > 1){
    for (let i = 0; i <num; i++){
      queue.enqueue(queue.dequeue())
    }
    eliminated = queue.dequeue()
    console.log(eliminated,"在遊戲被淘汰" );
  }
  return queue.dequeue()
}

var names = ['John', "stack", "Camila", " ingrid", "Carl"]
var winner = hotPotato(names, 7)